package leetcode.string;

import java.util.ArrayList;
import java.util.List;

public class Lc22 {
    List<String> ans = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        generateParenthesis(n, "", 0, 0);
        return ans;
    }

    private void generateParenthesis(int n, String s, int l, int r) {
        if (r == n) {
            ans.add(s);
            return;
        }
        if (l == r) generateParenthesis(n, s + "(", l + 1, r);
        else {
            if (l < n) generateParenthesis(n, s + "(", l + 1, r);
            if (l > r) generateParenthesis(n, s + ")", l, r + 1);
        }
    }


}
